package com.dataStructure.Map;




import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

//不用数据结构写
public class LRUTest {

}

class LRUCache {
    Deque<Integer> deque;
    int capacity ;
    Map<Integer, Integer> map;
    public LRUCache(int capacity) {
        deque = new LinkedList<Integer>();
        this.capacity = capacity;
        map = new HashMap<>();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return  -1;
        }
        //存在
        boolean remove = deque.remove(key);
        deque.addFirst(key);
        return map.get(key);

    }
    //一、不存在时
    //1. 超出容量
    //2. 没有超出容量

    //存在时和get逻辑一样
    public void put(int key, int value) {
        if (!map.containsKey(key)) {
            //说明超出了，要淘汰最后一个
            if (deque.size() == this.capacity) {
                Integer delKey = deque.removeLast();
                map.remove(delKey);
            }
            //小于，直接添加
            map.put(key, value);
            deque.addFirst(key);
        }

        //包括key
        else {
            map.put(key,value);
            deque.remove(key);
            deque.addFirst(key);;
        }
    }
}